#!/usr/bin/python
# author: andreas.kuntz@gmail.com
# you found this code on http://yoshiii-box.googlecode.com/svn/ 
#
m = 16          # length of BloomFilter Array
k = 5		# number of hash functions to apply to each string
n = 0		# number of inserted strings (counter)

def simple_string_hash(string):
	"calculates a really simple string hash"
        return sum(map(ord, tuple(string))) % m

def k_md5_hash(string):
	"performs k 'different' hash operations on <string>"
	from md5 import md5
	h = md5()
	for i in range(k):
		h.update(string)
		yield simple_string_hash(h.hexdigest())

k_hash = k_md5_hash

class CountingBloomFilter:
	def __init__(self):
		self.array = [0] * m
		
	def add(self, string):
		global n
		"add a new string to the bloom filter"
		for h in k_hash(string):
			self.array[h] += 1
		n += 1

	def remove(self, string):
		"remove a string from the boom filter"
		if not self.contains(string):
			raise ValueError("BloomFilter does not contain string '%s'"%string)
		for h in k_hash(string):
			self.array[h] -= 1

	def contains(self, string):
		"test if the bloom filter contains <string>"
		# get an array of the k corresponding hash values
		a = map(self.array.__getitem__, k_hash(string))
		# multiply the values => zero if all values are zero
		return reduce(lambda x,y: x*y, a) > 0

	def prob_false_positive(self):
		return (1 - (1-1.0/m)**(k*n) ) ** k		

	def print_status(self):
		print self.array
		print "m=%i"%m,"k=%i"%k,"n=%i,"%n,"P(FP) =", self.prob_false_positive()

BloomFilter = CountingBloomFilter

def module_test():
	bf = BloomFilter()
	def add():
		item = raw_input("fill BloomFilter with ")
		while item != '':
			bf.add(item)
			bf.print_status()
			item = raw_input("fill BloomFilter with ")

	def contains():
		item = raw_input("test BloomFilter for ")
		while item != '':
			print bf.contains(item)
			bf.print_status()
			item = raw_input("test BloomFilter for ")

	def remove():
		item = raw_input("remove from BloomFilter ")
		while item != '':
			bf.remove(item)
			bf.print_status()
			item = raw_input("remove from BloomFilter ")
	
	add()
	contains()
#	remove()
#	contains()

if __name__ == '__main__':
	module_test()
